An instruction scheduling queue is used to store instructions prior to execution. There are many different ways to manage the dispatch order, or age, of instructions in an instruction scheduling queue. A common queue implementation uses a first-in-first-out (FIFO) data structure. In this implementation, instruction dispatches arrive at the tail, or end, of the FIFO data structure. A look-up mechanism finds the first instruction ready for issue from the head, or start, of the FIFO data structure.
In conventional out-of-order implementations instructions are selected from anywhere in the FIFO data structure. This creates “holes” in the FIFO data structure at the locations of the selected instructions. To maintain absolute ordering of instruction dispatches in the FIFO data structure (e.g., for fairness), all of the remaining instructions after the selected instructions are shifted forward in the FIFO, and the data structure is collapsed to form a contiguous chain of instructions. Shifting and collapsing the remaining queue entries in this manner allows new entries to be added to the tail, or end, of the FIFO data structure. However, with a robust out-of-order issue rate, several instructions are shifted and collapsed every cycle. Hence, maintaining a contiguous sequence of queue entries without “holes” consumes a significant amount of power and processing resources.